This invention relates to arbitrations of priority requests for access to system resources and particularly to bus arbitration, especially star bus arbitration, a process for resolving the assignment of one of a plurality of simultaneous requestors for access to a system resource, usually a system bus. Once a requestor (device or processor) is given control of the resource, it can occupy it until the task is completed or for a predetermined period of time.
Electronic computer systems usually require that the processor have access to input and output devices for useful functioning. For most efficient operation, such devices operate independently from the central processor. That is, unlike early computer systems where the devices were controlled by the central processing unit, modern design moves the processing function into the device, permitting the central processor and the devices to function simultaneously and independently. At times, however, the devices must access resources shared with other devices and with the central processor. For example, the main memory is often a shared resource and is accessed via a system bus. The central processor operates on data stored in the memory and some devices are used to store data from outside the system into the memory for processing while other devices read data from the memory for use outside the system, e.g., printing the results of computation and processing.
To reduce interference with the workings of the central processor, a technique known as Direct Memory Access (DMA) is used to enable devices to read from or to write to the memory without requiring the central processor's intervention. The address of the data location in memory is stored in the device (or a channel through which the device operates) and used to address the memory during one or more cycles while the central processor and other devices are inhibited from accessing the memory. The DMA process operates as an interrupt procedure, so called because it doesn't always require access to the memory on a regular, periodic basis and interrupts the central system for access asynchronously. Such a process is also called cycle stealing.
All the devices, including the central processor, cannot access the memory bus simultaneously because there would be no way to distinguish the separate signals. Therefore, resource requests must be arbitrated in a way that fulfills the requirements of all the devices. Some devices operate at higher data rates than others. For example, a disk storage device can read and write data at a faster rate than a paper tape device. As a result, the high speed device needs faster and more frequent accesses to the memory bus than slow speed devices. Therefore, priority of access among devices is necessary.
The assignment of priorities to individual devices in a system is based on more than speed considerations. It is also necessary to prevent one or more high priority devices from crowding out a lower priority device to the extent that the latter does not obtain access to the systems resources sufficiently for proper operation or often enough resulting in lost data.
Using fixed priority schemes with hardware implementation has the advantage of high speed arbitration without interfering with the operation of the central processor. Using variable priority schemes under control of the central processor is more flexible but is slower and requires intervention of the central processor.
Several techniques of varying priority assignments have been developed including rotating priority among devices, using serial or polling procedures, and other complicated methods.
U.S. Pat. No. 4,229,791 discloses the use of individual arbitration circuits for controlling access to a common bus. Each circuit has a preassigned priority level but can be added or removed from the system or disabled without affecting the operation of the other units.
U.S. Pat. No. 4,257,095 discloses a shared system bus having an arbitration circuit that allows a lower priority device to access the system during times when a higher priority device, which has control of the system bus, is idle or accessing a bus other than the system bus.
U.S. Pat. No. 4,499,538 discloses a parallel, asynchronous arbitration of access requests which can be fixed priority, cyclic sequential, or mixed priority.
U.S. Pat. No. 4,716,523 discloses a programmably selective data transfer mode whereby the data transfer can be DMA mode or interrupt driven mode. DMA and character interrupt requests are arbitrated to pass control to a DMA controller or a character interrupt controller.
U.S. Pat. No. 4,418,974 discloses a priority system which stores the priority assignments in fixed memory locations with an addressing arrangement for addressing the memory locations cyclically and granting priority based on information stored with the priority assignments.
The invention avoids the disadvantages of a software-only or a hardware-only system by combining the advantages of both. It also avoids the problem of freezing out a slow, low priority requestor by limiting the number of successive accesses granted to the high priority requestors.
The invention has the ability to assign multiple requestors at the same priority level and resolve any conflicts while assigning a limit to the number of requestor's successive accesses, all during a single request/grant cycle.
In accordance with the invention, a system assigns priority access levels and sets associated bump values. When access requests are received, arbitration of the requests is made in accordance with the assigned priorities, bump values, and the received access requests. If a high priority level access request is granted, then the same request will be held off for a successive number of access grants as set by the bump values. In cases where access is required for more than one successive request/grant cycle, the priority level access can be retained as long as required.